package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 99. 恢复二叉搜索树
 * 给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,3,null,null,2]
 * 输出：[3,1,null,null,2]
 * 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [3,1,4,null,null,2]
 * 输出：[2,1,4,null,null,3]
 * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 */
public class RecoverTree {

    public void recoverTree(TreeNode root) {

        if (root == null) {
            return;
        }

        // 中序遍历
        List<Integer> nums = new ArrayList<>();
        inOrder(root, nums);

        // 找到翻转的节点数字
        int[] swap = findTwoSwap(nums);

        // 恢复
        recover(root, swap[0], swap[1]);
    }

    public void inOrder(TreeNode root, List<Integer> nums) {
        if (root != null) {
            inOrder(root.left, nums);
            nums.add(root.val);
            inOrder(root.right, nums);
        }
    }

    // 可能相邻 可能间隔
    public int[] findTwoSwap(List<Integer> nums) {

        int[] aa = new int[2];
        int index1 = -1, index2 = -1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) {
                index2 = i + 1;
                if (index1 == -1) {
                    // 如果是-1 说明是第一个
                    index1 = i;
                } else {
                    break;
                }
            }
        }
        aa[0] = nums.get(index1);
        aa[1] = nums.get(index2);
        return aa;
    }

    // 恢复，即深度遍历，碰到值就置换
    public void recover(TreeNode root, int x, int y) {
        if (root != null) {
            if (root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
            }
            recover(root.right, x, y);
            recover(root.left, x, y);
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }
}
